A communications system generally adopts channel encoding to improve reliability of data transmission, and ensure quality of communications. A Polar code (polar code) is an encoding mode that may obtain Shannon capacity and have low encoding and decoding complexity. The Polar code is a linear block code. Its generating matrix is GN., and its encoding process is x1N=u1NGN., where GN.=BNF⊗n, and a code length N=2n, n≥0.
      F    =          [                                    1                                0                                                1                                1                              ]        ,and BN is a transposed matrix, for example, a bit reversal (bit reversal) matrix.
F⊗n is a kronecker power (Kronecker power) of F, and is defined as F⊗n=F⊗F⊗ (n−1). The Polar code may be expressed as (N,K,A,uAC) by using a coset code, and the encoding process of the Polar code is x1N=uAGN. (A)⊕uACGN. (AC), where A is a set of an information (information) bit index, GN.(A) is a submatrix obtained through a row corresponding to an index in set A in GN., and GN.(AC) is a submatrix obtained through a row corresponding to an index in set AC in GN.uAC indicates frozen (frozen) bits, the number of uAC is (N−K), and uAC indicates known bits. For simpleness, the frozen bits may be set to 0.
The decoding of the Polar code may use SC (successive-cancellation, successive-cancellation) decoding. A process of the decoding of the Polar code is as follows:
A Polar code is considered, and a parameter of the Polar code is (N,K,A,uAC).
In SC decoding, the following conditional likelihood functions are calculated successively:
                                          L            N                          (              i              )                                ⁡                      (                                          y                1                N                            ,                                                u                  ^                                1                                  i                  -                  1                                                      )                          ⁢                  =          △                ⁢                                            W              N                              (                i                )                                      ⁡                          (                                                y                  1                  N                                ,                                                                            u                      ^                                        1                                          i                      -                      1                                                        ❘                  0                                            )                                                          W              N                              (                i                )                                      ⁡                          (                                                y                  1                  N                                ,                                                                            u                      ^                                        1                                          i                      -                      1                                                        ❘                  1                                            )                                                          (        1        )            
y1N is a received signal vector (y1, y2, . . . , yN), and u1i−1 is a bit vector (u1, u2, . . . , ui−1). W is a transition probability, and L indicates a log-likelihood ratio.
If i⊂A, a decision is made as follows:
                                          u            ^                    i                =                  {                                                                      0                  ,                                                                                                  If                    ⁢                                                                                  ⁢                                                                  L                        N                                                  (                          i                          )                                                                    ⁡                                              (                                                                              y                            1                            N                                                    ,                                                                                    u                              ^                                                        1                                                          i                              -                              1                                                                                                      )                                                                              ≥                  1                                                                                                      1                  ,                                                            Others                                                                        (        2        )            If i⊂AC,simply makeûi=ui  (3)
In the foregoing formulas (2) and (3), ûi indicates a decision value of bit ui.
The complexity of the SC decoding is O(N log2N). When a code length N is very long, the SC decoding can achieve good performance, which approaches a Shannon limit. However, when N is short or is of a medium length, the performance of the SC decoding of the Polar code does not exceed the performance of a Turbo code or an LDPC (Low-density Parity-check, low-density parity-check) code, and the decoding performance needs to be further improved.
In the SC decoding, the decoding is performed bit by bit. After each bit is decoded completely, a hard decision is performed, and a result of the hard decision is to be used by the decoding of a subsequent bit. In this way, error propagation may exist, thereby causing degradation of the decoding performance. List (list) decoding reserves multiple candidate paths and can achieve decoding performance that approaches maximum likelihood. The SC decoding and the List decoding are combined to obtain SC-List decoding.
A process of the SC-List decoding of the Polar code is briefly described as follows:
Path splitting: Each time, if ûi indicates information bits, a current decoding path is split into two paths; one path ûi=0 and the other path ûi=1. When the total number of the paths exceeds a predefined threshold L, a most unreliable path is discarded, and only L most reliable paths (called survivor paths) are kept; and probability values on all of the paths are updated. L is a positive integer, and may be called the number of the survivor paths.
No path splitting: If ûi indicates frozen bits, no decoding path is split, ûi=ui is set, the number of paths remains unchanged, and probability values on all of the paths are updated.
The complexity of the SC-List decoding is O(L×N×log 2N), and is about L times of the complexity of the SC decoding.
The Polar code obtained according to the foregoing manner quite adapts to simple SC decoding, but a minimum code distance of the Polar code is not very large. Even if optimal ML (Maximum Likelihood, maximum likelihood) decoding performance is achieved by adopting an improved SC-List decoding algorithm, its performance is not ideal, and a CRC (Cyclic Redundancy Check, cyclic redundancy check) must be cascaded to increase the minimum code distance. In this way, the performance and the application complexity of the Polar code are impacted.